package org.kfive.nova.algorithm;

import com.google.common.base.Strings;

import java.util.ArrayList;
import java.util.List;

/*
* LCS.java
* Created  by  lizhanwu
* Created on 2016-6-12 11:29
*/
public class LCS {

    private String source;

    private String target;

    private int [] [] martix;

    private String [][] trackMartix;

    private List<Character> result = new ArrayList<Character>();

    public LCS(String source,String target){
        this.source = source;
        this.target = target;
        this.martix = new int [this.source.length()+1][this.target.length()+1];
        this.trackMartix = new String [this.source.length()+1][this.target.length()+1];
    }

    public List<Character> longestSubSequence(){
        if(Strings.isNullOrEmpty(this.source)||Strings.isNullOrEmpty(this.target)){
            return result;
        }
        //初始化martix
        for (int i =0 ; i<this.source.length();i++){
            this.martix[i][0]=0;
        }
        for (int j = 0 ;j>this.target.length();j++){
            this.martix[0][j]=0;
        }
        //构建二维矩阵
        for (int i =1;i<=this.source.length();i++){
            for (int j =1;j<=this.target.length();j++){
                if(this.source.charAt(i-1)==this.target.charAt(j-1)){
                    this.martix[i][j]=this.martix[i-1][j-1]+1;
                    this.trackMartix[i][j]="leftup";
                }else{
                    if(this.martix[i-1][j]>=this.martix[i][j-1]){
                        this.martix[i][j] = this.martix[i-1][j];
                        this.trackMartix[i][j]="left";
                    }else{
                        this.martix[i][j] = this.martix[i][j-1];
                        this.trackMartix[i][j]="up";
                    }
                }
            }
        }
        //查找最长序列
        backTrack(this.source.length(),this.target.length());
        return result;
    }

    private void backTrack(int i,int j){
        if(i==0||j==0){
            return ;
        }
        if("leftup".equals(this.trackMartix[i][j])){
            this.result.add(this.source.charAt(i-1));
            backTrack(i-1,j-1);
        }else {
            if("left".equals(this.trackMartix[i][j])){
                backTrack(i-1,j);
            }else{
                backTrack(i,j-1);
            }
        }
    }

    public static void main(String[] args) {
        LCS lcs = new LCS("acgbfhk","cegefkh");
        List<Character> result = lcs.longestSubSequence();
        System.out.println(result);
    }
}
